# 38/100 二叉树-翻转二叉树
# leetcode第226题: https://leetcode.cn/problems/invert-binary-tree/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/9
from typing import Optional
from collections import deque
from leetcode.bds import TreeNode, TreeConverter
import leetcode.test as test


def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root:
        return []
    # 层序遍历, 每层的节点逐个调换左右节点
    queue = deque([root])

    while queue:
        n = len(queue)
        for i in range(n):
            cur = queue.popleft()
            cur.left, cur.right = cur.right, cur.left
            if cur.left:
                queue.append(cur.left)
            if cur.right:
                queue.append(cur.right)
    return TreeConverter.tree_to_list(root)


if __name__ == '__main__':
    t1 = TreeConverter.list_to_tree([4, 2, 7, 1, 3, 6, 9])
    t2 = TreeConverter.list_to_tree([2, 1, 3])
    t3 = None
    inp = [{"root": t1}, {"root": t2}, {"root": t3}, ]
    out = [[4, 7, 2, 9, 6, 3, 1], [2, 3, 1], [], ]
    test.test_function(invertTree, inp, out)
